word RAM model

Definition

Define an algorithm in the word RAM model of computation as follows:

Input, output, working memory are each represented as arrays. Initially, input is written while the output and working memory are blank.
Each entry in an array can store an integer or floating-point number (or arbitrary-precision real numbers) represented in binary up to a certain length. Or, entries may store characters (e.g. ASCII, Unicode).
Maximum number of bits per entry is called the word size
word is the unit of operations, $w \geq \log n$ for problem size $n$

Algorithm is sequence of instructions each executing in constant time $O(1)$ , e.g.

arithmetic operations on entries of arrays: add, subtract, multiply, divide, remainder, floor ceiling
- operations in constant time for numbers fitting in arrays
- exponentiation may require more care
condition checks and branches (e.g. if statements)
accessing any element of an array if we have its index (address) stored in a known location, this is the random access memory (RAM) component of the model. If array lengths $\geq m$ , then location index requires $\lceil\log_2 (m) \rceil$ bits to write down, word size at least this large.

We may further distinguish these operations taking constant time, by their circuit complexity:

$\mathbf{AC}^0$ operations (see AC0): polynomial-size circuit in $O(1)$ depth; bitwise logical operations, addition, subtraction, comparison, most significant bit
$\mathbf{AC}^1$ : multiplication, division

Rank operation

The Rank operation is performed on the packed word $X$ containing $k$ keys, and the objective is to find the number of keys with value greater than $q$ . Hence, by subtracting $\hat q$ = [0 q | 0 q | ... | 0q] from $X$ , where $X$ = [ 1 x_1 | 1 x_2 | ... | 1 x_k ] we obtain the rank from [c1 | 0 | c_2 | 0 ...] number of $c_i = 1$ due to borrowing which would make $c_i = 0$ if $x_{i} < q$ . Hence this is considered $O(1)$ by using $AC_0$ operations of subtraction and significant bits.

Notes

word size $w$ is an important parameter of the model, assuming $w \geq \log n$ , $n$ number of elements stored in any of the data structures
packed word when #incomplete

word RAM model

Definition

Rank operation

Notes

See also

References